skip to main content

Explore Research Products in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Millman, David L."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; ; ; ( , Young Researcher's Forum at CG Week)
    Blank, in his Ph.D. thesis on determining whether a planar closed curve $\gamma$ is self-overlapping, constructed a combinatorial word geometrically over the faces of $\gamma$ by drawing cuts from each face to a point at infinity and tracing their intersection points with $\gamma$. Independently, Nie, in an unpublished manuscript, gave an algorithm to determine the minimum area swept out by any homotopy from a closed curve $\gamma$ to a point. Nie constructed a combinatorial word algebraically over the faces of $\gamma$ inspired by ideas from geometric group theory, followed by dynamic programming over the subwords. In this paper, we examine the definitions of the two words and prove the equivalence between Blank's word and Nie's word under the right assumptions. 
    more » « less
    Free, publicly-accessible full text available June 12, 2024
  2. ; ; ; ; ( , Canadian Conference on Computational Geometry (CCCG))
    Persistent homology is a tool that can be employed to summarize the shape of data by quantifying homological features. When the data is an object in R d , the (augmented) persistent homology transform ((A)PHT) is a family of persistence diagrams, parameterized by directions in the ambient space. A recent advance in understanding the PHT used the framework of reconstruction in order to find finite a set of directions to faithfully represent the shape, a result that is of both theoretical and practical interest. In this paper, we improve upon this result and present an improved algorithm for graph— and, more generally one-skeleton—reconstruction. The improvement comes in reconstructing the edges, where we use a radial binary (multi-)search. The binary search employed takes advantage of the fact that the edges can be ordered radially with respect to a reference plane, a feature unique to graphs. 
    more » « less
    Accepted Manuscript Full Text Available
  3. ; ; ; ( , Applications of Topological Data Analysis to Data Science, Artificial Intelligence, and Machine Learning (TDA at SDM))
    Since its introduction in the mid-1990s, DBSCAN has become one of the most widely used clustering algorithms. However, one of the steps in DBSCAN is to perform a range query, a task that is difficult in many spaces, including the space of persistence diagrams. In this paper, we introduce a spanner into the DBSCAN algorithm to facilitate range queries in such spaces. We provide a proof-of-concept implementation, and study time and clustering performance for two data sets of persistence diagrams. 
    more » « less
    Accepted Manuscript Full Text Available
  4. ; ; ( , Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG 2020))
    Given a simplicial complex K and an injective function f from the vertices of K to R, we consider algorithms that extend f to a discrete Morse function on K. We show that an algorithm of King, Knudson and Mramor can be described on the directed Hasse diagram of K. Our description has a faster runtime for high dimensional data with no increase in space. 
    more » « less
    Accepted Manuscript Full Text Available
  5. ; ; ; ; ; ; ; ; ( , Computational Geometry)
    Full Text Available 
  6. ; ; ; ; ; ; ; ; ( , Canadian Conference on Computational Geometry)
    Topological Data Analysis (TDA) studies the “shape” of data. A common topological descriptor is the persistence diagram, which encodes topological features in a topological space at different scales. Turner, Mukherjee, and Boyer showed that one can reconstruct a simplicial complex embedded in R^3 using persistence diagrams generated from all possible height filtrations (an uncountably infinite number of directions). In this paper, we present an algorithm for reconstructing plane graphs K = (V, E) in R^2, i.e., a planar graph with vertices in general position and a straight-line embedding, from a quadratic number height filtrations and their respective persistence diagrams. 
    more » « less
    Accepted Manuscript Full Text Available